-
Notifications
You must be signed in to change notification settings - Fork 73
Expand file tree
/
Copy path6.824 Lab 3_ Fault-tolerant Key_Value Service.html
More file actions
533 lines (464 loc) · 19.6 KB
/
Copy path6.824 Lab 3_ Fault-tolerant Key_Value Service.html
File metadata and controls
533 lines (464 loc) · 19.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
<!DOCTYPE html>
<!-- saved from url=(0056)http://nil.csail.mit.edu/6.824/2020/labs/lab-kvraft.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<link rel="stylesheet" href="./assets/style.css" type="text/css">
<title>6.824 Lab 3: Fault-tolerant Key/Value Service</title>
</head>
<body>
<div align="center">
<h2><a href="http://nil.csail.mit.edu/6.824/2020/index.html">6.824</a> - Spring 2020</h2>
<h1>6.824 Lab 3: Fault-tolerant Key/Value Service</h1>
<h3>Due Part A: Apr 3 23:59</h3>
<h3>Due Part B: Apr 17 23:59</h3>
</div>
<hr>
<h3>Introduction</h3>
<p>
In this lab you will build a fault-tolerant key/value storage
service using your Raft library from
<a href="http://nil.csail.mit.edu/6.824/2020/labs/lab-raft.html">lab 2</a>. Your
key/value service will be a replicated state machine, consisting of
several key/value servers that use Raft for replication.
Your key/value service should continue to
process client requests as long as a majority of the servers
are alive and can communicate, in spite of other failures or
network partitions.
</p><p>
The service supports three operations: <tt>Put(key, value)</tt>,
<tt>Append(key, arg)</tt>, and <tt>Get(key)</tt>. It maintains a
simple database of key/value pairs. Keys and values are strings.
<tt>Put()</tt> replaces the value
for a particular key in the database, <tt>Append(key, arg)</tt>
appends arg to key's value, and <tt>Get()</tt> fetches the current
value for a key. A <tt>Get</tt> for a non-existant key should return
an empty string. An <tt>Append</tt> to a non-existant key should act
like <tt>Put</tt>. Each client talks to the service through
a <tt>Clerk</tt> with Put/Append/Get methods. A <tt>Clerk</tt> manages
RPC interactions with the servers.
</p><p>
Your service must provide strong consistency to application calls to
the <tt>Clerk</tt> Get/Put/Append methods. Here's what we mean by
strong consistency. If called one at a time, the Get/Put/Append
methods should act as if the system had only one copy of its state,
and each call should observe the modifications to the state implied by
the preceding sequence of calls. For concurrent calls, the return
values and final state must be the same as if the operations had
executed one at a time in some order. Calls are concurrent if they
overlap in time, for example if client X calls <tt>Clerk.Put()</tt>,
then client Y calls <tt>Clerk.Append()</tt>, and then client X's call
returns. Furthermore, a call must observe the effects of all calls
that have completed before the call starts (so we are technically
asking for linearizability).
</p><p>
Strong consistency is convenient for applications because it means
that, informally, all clients see the same state and they all see the
latest state. Providing strong consistency is relatively easy for
a single server. It is harder if the service is replicated,
since all servers must choose the same execution order for
concurrent requests, and must avoid replying to clients using state
that isn't up to date.
</p><p>
This lab has two parts. In part A, you will implement the
service without worrying that the Raft log can grow without
bound. In part B, you will implement snapshots (Section 7 in
the paper), which will allow Raft to discard old log
entries. Please submit each part by the respective deadline.
</p><p>
You should reread the
<a href="http://nil.csail.mit.edu/6.824/2020/papers/raft-extended.pdf">extended Raft paper</a>,
in particular Sections 7 and 8. For a wider
perspective, have a look at Chubby, Paxos Made Live,
Spanner, Zookeeper, Harp, Viewstamped Replication, and
<a href="http://static.usenix.org/event/nsdi11/tech/full_papers/Bolosky.pdf">Bolosky et al.</a>
</p><p>
Start early.
</p><h3>Collaboration Policy</h3>
You must write all the code you hand in for 6.824, except for
code that we give you as part of the assignment. You are not
allowed to look at anyone else's solution, you are not allowed
to look at code from previous years, and you are not allowed to
look at other Raft implementations. You may discuss the
assignments with other students, but you may not look at or
copy each others' code.
<p>
Please do not publish your code or make
it available to current or future 6.824 students.
<tt>github.com</tt> repositories are public by default, so please
don't put your code there unless you make the repository private. You
may find it convenient to use
<a href="https://github.mit.edu/">MIT's GitHub</a>,
but be sure to create a private repository.
</p><h3>Getting Started</h3>
<p>
We supply you with skeleton code and tests in <tt>src/kvraft</tt>. You will
need to modify <tt>kvraft/client.go</tt>, <tt>kvraft/server.go</tt>, and
perhaps <tt>kvraft/common.go</tt>.
</p><p>
To get up and running, execute the following commands.
Don't forget the <tt>git pull</tt> to get the latest software.
</p><pre>$ cd ~/6.824
$ git pull
...
$ cd src/kvraft
$ go test
...
$</pre>
<h3>Part A: Key/value service without log compaction</h3>
<p>
Each of your key/value servers ("kvservers") will have an associated
Raft peer. Clerks send <tt>Put()</tt>, <tt>Append()</tt>,
and <tt>Get()</tt> RPCs to the kvserver whose associated Raft is the
leader. The kvserver code submits the Put/Append/Get operation to
Raft, so that the Raft log holds a sequence of Put/Append/Get
operations. All of the kvservers execute operations from the Raft log
in order, applying the operations to their key/value databases; the
intent is for the servers to maintain identical replicas of the
key/value database.
</p><p>
A <tt>Clerk</tt> sometimes doesn't
know which kvserver is the Raft leader. If the <tt>Clerk</tt> sends an
RPC to the wrong kvserver, or if it cannot reach the kvserver,
the <tt>Clerk</tt> should re-try by sending to a different kvserver.
If the key/value service commits the operation to its Raft log
(and hence applies the operation to the key/value state machine), the
leader reports the result to the <tt>Clerk</tt> by responding to its
RPC. If the operation failed to commit (for example, if the leader was
replaced), the server reports an error, and the <tt>Clerk</tt> retries with a
different server.
</p><p>
Your kvservers should not directly communicate; they
should only interact with each other through Raft.
For all parts of Lab 3, you must make sure that your
Raft implementation continues to pass all of the
Lab 2 tests.
</p><div class="todo">
<p>
Your first task is to implement a solution that works when there are no dropped
messages, and no failed servers.
</p><p>
You'll need to add RPC-sending code to the Clerk Put/Append/Get
methods in <tt>client.go</tt>, and implement
<tt>PutAppend()</tt> and <tt>Get()</tt> RPC handlers in
<tt>server.go</tt>. These handlers should enter an
<tt>Op</tt> in the Raft log using <tt>Start()</tt>; you should fill in
the <tt>Op</tt> struct definition in <tt>server.go</tt> so that it
describes a Put/Append/Get operation. Each server should
execute <tt>Op</tt> commands as Raft commits them, i.e.
as they appear on the <tt>applyCh</tt>. An RPC handler
should notice when Raft commits its <tt>Op</tt>, and then reply to the
RPC.
</p><p>
You have completed this task when you
<strong>reliably</strong> pass the first test in the
test suite: "One client".
</p></div>
<ul class="hints">
<li>
After calling <tt>Start()</tt>, your
kvservers will need to wait for Raft to complete
agreement. Commands that have been agreed upon arrive
on the <tt>applyCh</tt>. Your
code will need to
keep reading <tt>applyCh</tt> while
<tt>PutAppend()</tt> and <tt>Get()</tt> handlers submit
commands to the Raft log using <tt>Start()</tt>.
Beware of deadlock between the kvserver and its
Raft library.
</li><li>
You are allowed to add fields to the Raft <tt>ApplyMsg</tt>,
and to add fields to Raft RPCs such as <tt>AppendEntries</tt>.
</li><li>
A kvserver should not complete a <tt>Get()</tt>
RPC if it is not part of a majority (so that it does
not serve stale data). A simple solution is to enter
every <tt>Get()</tt> (as well as each <tt>Put()</tt>
and <tt>Append()</tt>) in the Raft log. You don't have
to implement the optimization for read-only operations
that is described in Section 8.
</li><li>
It's best to add locking from the start because the
need to avoid deadlocks sometimes affects overall code design. Check
that your code is race-free using
<tt>go test -race</tt>.
</li></ul>
Now you should modify your solution to continue in the face of network
and server failures.
One problem you'll face is that a
<tt>Clerk</tt> may have to send an RPC multiple times until it finds a
kvserver that replies positively. If a leader fails just after
committing an entry to the Raft log, the <tt>Clerk</tt> may not
receive a reply, and thus may
re-send the request to another leader.
Each call to
<tt>Clerk.Put()</tt> or <tt>Clerk.Append()</tt> should
result in just a single execution, so you will have to ensure
that the re-send doesn't result in the servers executing
the request twice.
<p class="todo">
Add code to handle failures, and
to cope with duplicate <tt>Clerk</tt> requests, including
situations where the <tt>Clerk</tt> sends a request to a kvserver leader
in one term, times out waiting for a reply, and re-sends the
request to a new leader in another term. The request
should execute just once.
Your code should pass the <tt>go test -run 3A</tt> tests.
</p><ul class="hints">
<li>
Your solution needs to handle a
leader that has called Start() for a Clerk's
RPC, but loses its leadership before the
request is committed to the log. In this case
you should arrange for the Clerk to re-send
the request to other servers until it finds
the new leader. One way to do this is for the
server to detect that it has lost leadership,
by noticing that a different request has
appeared at the index returned by Start(), or
that Raft's term has
changed. If the ex-leader is partitioned by
itself, it won't know about new leaders; but
any client in the same partition won't be able
to talk to a new leader either, so it's OK in
this case for the server and client to wait
indefinitely until the partition heals.
</li><li>
You will probably have to modify your
Clerk to remember which server turned out to
be the leader for the last RPC, and send the
next RPC to that server first. This will avoid
wasting time searching for the leader on every
RPC, which may help you pass some of the tests
quickly enough.
</li><li>
You will need to uniquely identify client operations to ensure that
the key/value service executes each one just once.
</li><li>
Your scheme for duplicate detection should free server memory quickly,
for example by having each RPC imply that the client has seen the
reply for its previous RPC. It's OK to assume that a client will make
only one call into a Clerk at a time.
</li></ul>
<p>
Your code should now pass the Lab 3A tests, like this:
</p><pre>$ go test -run 3A
Test: one client (3A) ...
... Passed -- 15.1 5 12882 2587
Test: many clients (3A) ...
... Passed -- 15.3 5 9678 3666
Test: unreliable net, many clients (3A) ...
... Passed -- 17.1 5 4306 1002
Test: concurrent append to same key, unreliable (3A) ...
... Passed -- 0.8 3 128 52
Test: progress in majority (3A) ...
... Passed -- 0.9 5 58 2
Test: no progress in minority (3A) ...
... Passed -- 1.0 5 54 3
Test: completion after heal (3A) ...
... Passed -- 1.0 5 59 3
Test: partitions, one client (3A) ...
... Passed -- 22.6 5 10576 2548
Test: partitions, many clients (3A) ...
... Passed -- 22.4 5 8404 3291
Test: restarts, one client (3A) ...
... Passed -- 19.7 5 13978 2821
Test: restarts, many clients (3A) ...
... Passed -- 19.2 5 10498 4027
Test: unreliable net, restarts, many clients (3A) ...
... Passed -- 20.5 5 4618 997
Test: restarts, partitions, many clients (3A) ...
... Passed -- 26.2 5 9816 3907
Test: unreliable net, restarts, partitions, many clients (3A) ...
... Passed -- 29.0 5 3641 708
Test: unreliable net, restarts, partitions, many clients, linearizability checks (3A) ...
... Passed -- 26.5 7 10199 997
PASS
ok kvraft 237.352s
</pre>
<p>
The numbers after each <tt>Passed</tt> are real time in seconds,
number of peers, number of RPCs sent (including client RPCs), and
number of key/value operations executed (<tt>Clerk</tt> Get/Put/Append
calls).
</p><h3>Handin procedure for lab 3A</h3>
<p>
Run the tests for part A one final time.
Run <tt>make lab3a</tt> to upload your code
to the submission website at
<a href="https://6824.scripts.mit.edu/2020/handin.py/">https://6824.scripts.mit.edu/2020/handin.py/</a>.
</p><p>
You may use your MIT Certificate or request an API key via
email to log in for the first time. Your API key (<tt>XXX</tt>)
is displayed once you are logged in, and can be used to upload
the lab from the console as follows.
</p><pre>$ cd ~/6.824
$ echo "XXX" > api.key
$ make lab3a</pre>
<p>
Check the submission website to make sure it sees your submission.
</p><p>
You may submit multiple times. We will use the timestamp of
your <strong>last</strong> submission for the purpose of
calculating late days. Your grade is determined by the score
your solution <strong>reliably</strong> achieves when we run
the tests.
</p><h3>Part B: Key/value service with log compaction</h3>
<p>
As things stand now with your code, a rebooting server replays the
complete Raft log in order to restore its state. However, it's not
practical for a long-running server to remember the complete Raft log
forever. Instead, you'll modify Raft and kvserver to cooperate to save
space: from time to time kvserver will persistently store a "snapshot"
of its current state, and Raft will discard log entries that precede
the snapshot. When a server restarts (or falls far behind the leader
and must catch up), the server first installs a snapshot and then
replays log entries from after the point at which the snapshot
was created.
Section 7 of the
<a href="http://nil.csail.mit.edu/6.824/2020/papers/raft-extended.pdf">extended Raft paper</a>
outlines the scheme; you will have to design the details.
</p><p>
You must design an
interface between your Raft library and your
service that allows your Raft library to discard log
entries. You must revise your Raft code to operate while
storing only the tail of the log.
Raft should discard old log entries in a
way that allows the Go garbage collector to free and
re-use the memory; this requires that there be no
reachable references (pointers) to the discarded log
entries.
</p><p>
The tester passes <tt>maxraftstate</tt> to your
<tt>StartKVServer()</tt>. <tt>maxraftstate</tt> indicates the maximum
allowed size of your persistent Raft state in bytes (including the
log, but not including snapshots). You should
compare <tt>maxraftstate</tt> to <tt>persister.RaftStateSize()</tt>.
Whenever your key/value server detects that the Raft state size is
approaching this threshold, it should save a snapshot, and tell the
Raft library that it has snapshotted, so that Raft can discard old log
entries. If <tt>maxraftstate</tt> is -1, you do not have to snapshot.
<tt>maxraftstate</tt> applies to the GOB-encoded
bytes your Raft passes to <tt>persister.SaveRaftState()</tt>.
</p><p class="todo">
Modify your Raft so that it can be given a log index, discard the entries
before that index, and continue operating while storing only log
entries after that index. Make sure all the Lab 2 Raft tests still succeed.
</p><p class="todo">
Modify your kvserver so that it detects when the persisted
Raft state grows too large, and then hands a snapshot
to Raft and tells
Raft that it can discard old log entries.
Raft should
save each snapshot with persister.SaveStateAndSnapshot()
(don't use files).
A kvserver instance should restore the snapshot from the
persister when it re-starts.
</p><ul class="hints">
<li>
Think about when a kvserver should snapshot its state
and what should be included in the snapshot. Raft must
store each snapshot in the persister object using
<tt>SaveStateAndSnapshot()</tt>,
along with corresponding Raft state.
You can read the
latest stored snapshot using <tt>ReadSnapshot()</tt>.
</li><li>
Your kvserver must be able to detect
duplicated operations in the log across checkpoints, so any
state you are using to detect them must be included in
the snapshots.
</li><li>Capitalize all fields of structures stored in the snapshot.
</li><li>
You are allowed to add methods to your Raft so that
kvserver can manage the process of trimming the Raft
log and manage kvserver snapshots.
</li></ul>
<p class="todo">
Modify your Raft leader code to send an InstallSnapshot
RPC to a follower when the leader has discarded log
entries that the follower needs.
When a follower receives an InstallSnapshot RPC,
it must hand the included snapshot to
its kvserver. You can use the <tt>applyCh</tt>
for this purpose, by adding new fields to <tt>ApplyMsg</tt>.
Your
solution is complete when it passes all of the Lab 3 tests.
</p><ul class="hints">
<li>
Send the entire snapshot in a single InstallSnapshot RPC.
Don't implement Figure 13's <tt>offset</tt> mechanism for
splitting up the snapshot.
</li><li>
Make sure you pass <tt>TestSnapshotRPC</tt> before
moving on to the other Snapshot tests.
</li><li>
A reasonable amount of time to take for the Lab 3 tests is 400 seconds
of real time and 700 seconds of CPU time. Further,
<tt>go test -run TestSnapshotSize</tt> should take less than 20
seconds of real time.
</li></ul>
<p>
Your code should pass the 3B tests (as in the example here) as well
as the 3A tests (and your Raft must continue to pass the Lab 2 tests).
</p><pre>$ go test -run 3B
Test: InstallSnapshot RPC (3B) ...
... Passed -- 1.5 3 163 63
Test: snapshot size is reasonable (3B) ...
... Passed -- 0.4 3 2407 800
Test: restarts, snapshots, one client (3B) ...
... Passed -- 19.2 5 123372 24718
Test: restarts, snapshots, many clients (3B) ...
... Passed -- 18.9 5 127387 58305
Test: unreliable net, snapshots, many clients (3B) ...
... Passed -- 16.3 5 4485 1053
Test: unreliable net, restarts, snapshots, many clients (3B) ...
... Passed -- 20.7 5 4802 1005
Test: unreliable net, restarts, partitions, snapshots, many clients (3B) ...
... Passed -- 27.1 5 3281 535
Test: unreliable net, restarts, partitions, snapshots, many clients, linearizability checks (3B) ...
... Passed -- 25.0 7 11344 748
PASS
ok kvraft 129.114s
</pre>
<h3>Handin procedure for lab 3B</h3>
<p>
Double-check that your code passes all the tests.
Run <tt>make lab3b</tt> to upload your code
to the submission website, at
<a href="https://6824.scripts.mit.edu/2020/handin.py/">https://6824.scripts.mit.edu/2020/handin.py/</a>.
</p><p>
You may use your MIT Certificate or request an API key via
email to log in for the first time. Your API key (<tt>XXX</tt>)
is displayed once you logged in, which can be used to upload
the lab from the console as follows.
</p><pre>$ echo "XXX" > api.key
$ make lab3b</pre>
<p>
Check the submission website to make sure it sees your submission.
</p><p>
You may submit multiple times. We will use the timestamp of
your <strong>last</strong> submission for the purpose of
calculating late days. Your grade is determined by the score
your solution <strong>reliably</strong> achieves when we run
the tests.
</p><hr>
<address>
Please post questions on <a href="http://piazza.com/">Piazza</a>.
</address>
<!-- LocalWords: RPCs viewservice src pbservice cd view's PingInterval ack pb
-->
<!-- LocalWords: DeadPings Viewservice ViewServer PingArgs Viewnum viewservice
-->
<!-- LocalWords: Handin gzipped czvf whoami tgz TestBasicFail GetReply
-->
<!-- LocalWords: TestFailPut TestConcurrentSame TestPartition PutReply Raft
-->
<!-- LocalWords: instance's Viewstamped al paxos TestBasic seq Go's
-->
<!-- LocalWords: ndecided TestForget px int bool ok Min Raft's piggyback un
-->
<!-- LocalWords: struct Op IDs pm structs marshall unmarshall class's
-->
<!-- LocalWords: StartServer website API
-->
</body></html>